﻿/* 19. *** Write a program that reads a number N 
 * and generates and prints all the permutations of the numbers [1 … N]. */

using System;
using System.Numerics;

public class Permutations
{
    public static int n;
    public static BigInteger allPermutations;
    public static int[] elements;
    public static int digitsOfN;

    public static void Main()
    {
        do
        {
            DataInput();
            Calculations();
            AllPermutations();
            Console.Write("\nPress any key to show other permutations...");
            Console.ReadKey();

        } while (true);
    }

    public static void DataInput()
    {
        do
        {
            Console.Clear();
            Console.Write("\nPermutations\n\nN = ");
            if ((int.TryParse(Console.ReadLine(), out n) && (0 < n)))
                break;
        } while (true);
    }

    private static void AllPermutations()
    {
        BigInteger kEmptyPosition;
        int rightEmptyPosition;
        BigInteger structure;

        for (long row = 0; row < allPermutations; row++)
        {
            for (int i = 0; i < n; i++)
                elements[i] = 0;

            for (int element = n; element > 0; element--)
            {
                structure = allPermutations;
                for (int i = n; i >= element; i--)
                    structure /= i;

                kEmptyPosition = (row / structure) % element;

                rightEmptyPosition = -1;

                for (int i = 0; i < n; i++)
                {
                    if (elements[i] == 0)
                    {
                        rightEmptyPosition++;
                        if (rightEmptyPosition == kEmptyPosition)
                        {
                            elements[i] = n - element + 1;
                            break;
                        }
                    }
                }
            }

            Console.Write("{0}{1}", new string(' ', (digitsOfN - Digits(elements[0]))), elements[0]);
            for (int i = 1; i < n; i++)
                Console.Write(" {0}{1}", new string(' ', (digitsOfN - Digits(elements[i]))), elements[i]);

            Console.WriteLine();
        }
    }

    public static int Digits(int number)
    {
        int digits = 0;
        while (number > 0)
        {
            digits++;
            number /= 10;
        }

        return digits;
    }

    public static void Calculations()
    {
        allPermutations = n;
        for (int i = n - 1; i > 1; i--)
            allPermutations *= i;

        Console.WriteLine("\nAll Permutations are {0}.\n", allPermutations);
        System.Threading.Thread.Sleep(2000);

        digitsOfN = Digits(n);

        elements = new int[n];
    }
}